package pers.qianyu.month_202012.date_20201217;

import java.util.*;

/**
 * 710. 黑名单中的随机数
 * https://leetcode-cn.com/problems/random-pick-with-blacklist/
 *
 * @author mizzle rain
 * @date 2020年12月17日15:54:24
 */
public class Pick {
    private int size;
    private HashMap<Integer, Integer> dict;

    public Pick(int N, int[] blacklist) {
        size = N - blacklist.length;
        int last = N - 1;
        dict = new HashMap<>();

        for (int i : blacklist) {
            dict.put(i, 1);
        }
        for (int i : blacklist) {
            if (i >= size) {
                continue;
            }
            // [模糊]
            while (dict.containsKey(last)) {
                last--;
            }
            dict.put(i, last--);
        }
    }

    public int pick() {
        int index = new Random().nextInt(size);
        if (dict.containsKey(index)) {
            return dict.get(index);
        }
        return index;
    }
}